Having just added vertex $B$ and updated our frontier, the algorithm continues its simple, repetitive select-add-update cycle. This process repeats until all vertices are connected, which always occurs after $V-1$ edges have been added to the tree.

  • Let's trace the remaining selections:
    • The next cheapest edge is $(C, D)$ with weight 2. We add vertex $D$ and this edge to our MST.
    • We update the frontier with edges from $D$. The queue now contains $(A, B, 4)$, $(B, D, 5)$, $(C, E, 6)$, $(D, F, 7)$, $(D, E, 8)$.
    • The next choice is $(A, B, 4)$, but $B$ is already in the MST, so we discard it. Similarly, $(B, D, 5)$ is discarded.
    • The next valid choice is $(C, E, 6)$. We add vertex $E$.
    • Finally, the cheapest edge to an unvisited vertex is $(D, F, 7)$. We add vertex $F$.

At this point, we have added $V-1 = 5$ edges, and all 6 vertices are in our set. The algorithm terminates. The total weight of our MST is the sum of the weights of the selected edges: $3 + 1 + 2 + 6 + 7 = 19$.

Python Implementation (Prim's)
1import heapq
2
3def prims_algorithm(graph, start_node):
4    mst_vertices = {start_node}
5    priority_queue = []
6    mst_edges = []
7    total_weight = 0
8
9    # Add initial edges from the start node
10    for neighbor, weight in graph[start_node].items():
11        heapq.heappush(priority_queue, (weight, start_node, neighbor))
12
13    while priority_queue and len(mst_vertices) < len(graph):
14        weight, u, v = heapq.heappop(priority_queue)
15
16        if v not in mst_vertices:
17            mst_vertices.add(v)
18            mst_edges.append((u, v, weight))
19            total_weight += weight
20
21            for neighbor, neighbor_weight in graph[v].items():
22                if neighbor not in mst_vertices:
23                    heapq.heappush(priority_queue, (neighbor_weight, v, neighbor))
24    
25    return mst_edges, total_weight
26
27# Using the Shared_Graph definition
28shared_graph = {
29    'A': {'B': 4, 'C': 3}, 'B': {'A': 4, 'C': 1, 'D': 5},
30    'C': {'A': 3, 'B': 1, 'D': 2, 'E': 6}, 'D': {'B': 5, 'C': 2, 'E': 8, 'F': 7},
31    'E': {'C': 6, 'D': 8, 'F': 9}, 'F': {'D': 7, 'E': 9}
32}
33
34final_mst, final_weight = prims_algorithm(shared_graph, 'A')
35print(f"Final MST Edges: {final_mst}")
36print(f"Total MST Weight: {final_weight}")